# @Time    : 2020/6/27 9:21
# @Author  : T-
# @Site    : 
# @File    : 110-Balanced Binary Tree.py
# @Software: PyCharm

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def height(self, root: TreeNode) -> int:
        if not root:
            return -1
        return max(self.height(root.left), self.height(root.right)) + 1

    def isBalancedHelper(self, root: TreeNode) -> (bool, int):
        if not root:
            return True, -1
        leftIsBalanced, leftHeight = self.isBalancedHelper(root.left)
        if not leftIsBalanced:
            return False, 0
        rightIsBalanced, rightHeight = self.isBalancedHelper(root.right)
        if not rightIsBalanced:
            return False, 0
        return (abs(leftHeight - rightHeight) < 2), 1 + max(leftHeight, rightHeight)

    def isBalanced(self, root: TreeNode) -> bool:
        # method-1: 自顶向下的递归
        if root is None:
            return True
        return abs(self.height(root.left) - self.height(root.right)) < 2 \
               and self.isBalanced(root.left) \
               and self.isBalanced(root.right)

        # method-2: 自底向上的递归
        return self.isBalancedHelper(root)[0]